Міністерство освіти і науки України
Національний університет «Львівська політехніка»
В.О.Костовський
«ТЕОРІЯ АЛГОРИТМІВ ТА МАТЕМАТИЧНІ ОСНОВИ ПРЕДСТАВЛЕННЯ ЗНАНЬ»
М е т о д и ч н i в к а з i в к и д о к у р с у л е к ц і й
для студентів бакалаврату базового напрямку
“Комп‘ютнрні науки”
Кафедра “Автоматизовані системи управління”
Курс ІV
Львів -2002
Конспект лекцій по ТА МОПЗ - 2002/2003
Методичні вказівки склав
Доцент кафедри АСУ В.О.Костовський
(вчене звання, посада викладача)
(підпис)
(прізвище, ініціали)
"___"____________2002 р.
Методичні вказівки розглянуті та схвалені на засіданні кафедри
«Автоматизовані системи управління»
(найменування кафедри, за якою закріплена дисципліна)
Протокол №___ від "___"________________2002 р.
Завідувач кафедри
Рашкевич Ю.М.
(підпис)
(прізвище, ініціали)
ВСТУП
Ці методичні вказівки до курсу лекцій з курсу «Теорія алгоритмів та математичні основи представлення знань» (ТА МОПЗ) розроблені з метою полегшення вивчення студентами основних тем даного курса відповідно до програми з ТА МОПЗ. При викладі сутевим чином використовуються підходи робіт [1,2,3].
Тема "Алгоритмічні проблеми"
§1 Алгоритми обчислювальні процедури
Навчаючи арифметиці в початковій школі, ми познайомилися з додаванням і множенням двох чисел. Нам у явній формі не говорили, що в будь-якої пари чисел існують добуток і сума, а вказали способи і правила їхнього знаходження. Такі способи і правила є прикладами алгоритмів, і обчислювальних (ефективних) процедур. Їхнє застосування не вимагає чи винахідливості чи кмітливості, учню необхідно було тільки слідувати інструкціям учителя.
Більш загально, алгоритм, чи ефективна процедура,-це механічне правило чи автоматичний метод, чи програма для виконання деяких математичних операцій. Приведемо ще кілька прикладів операцій, для яких легко можна вказати алгоритми:
(1.1) (а) по даному п знайти n-e просте число;
(b) диференціювання полінома;
(c) знаходження найбільшого загального дільника двох натуральних чисел (алгоритм Евклида);
(d) для двох даних чисел х, у вирішити, чи є х кратним у.
Неформально і схематично алгоритм представлений на мал. 1а. На вхід подається інформація чи об'єкт, що підлягає обробці (наприклад, поліном у прикладі (1.1) (b), пари натуральних чисел у прикладах (1.1) (с) і (d)), а виходом є результат обробки операції над входом (так, для (1.1) (b) це похідна полінома, а для (1.1) (d)—відповідь «так» чи «ні»). Вихід виробляється автоматично чорним ящиком-який може бути комп'ютером або школярем, що діє по інструкції, чи навіть дуже розумним добре тренованим собакою. Алгоритм є процедура (чи спосіб обчислення), здійснювана чорним ящиком для одержання виходу з входу.
Якщо алгоритм, чи ефективна процедура, використовується для обчислення значень числової функції, то ця функція називається ефективно вычислимой, чи алгоритмічно вычислимой, чи просто вычислимой. Наприклад, функції ху,
Вхід вихід
НОД(х,у)= найбільший загальний дільник чисел х и у и f(n)= просте число вираховувані в неформальному змісті, як уже відзначалося вище.
Розглянемо, з іншого боку, наступну функцію:
1, якщо в десятковому розкладанні числа pi знайдеться
g(n)== рівно п підряд йдущих цифр 7;
0 у противному випадку.
Більшість математиків вважають, що g є цілком «законною» функцією. Але чи вираховувана функція g? Існує механічна процедура для послідовного породження цифр у десятковому розкладанні pi, тому напрошується «процедура» для обчислення функції g. «При заданому п почніть обчислювати десятковий розклад pi по одній цифрі за один такт часу і відзначайте появу сімок. Якщо на якому-небудь кроці з'явиться відрізок, що складається рівно з п сімок, зупините процес обчислення і покладете g(n}=0. Якщо такий відрізок не буде обнаружен, то покладете g(n)=0».
Недоліком цієї «...